﻿#define _CRT_SECURE_NO_WARNINGS 1

//hday15

//x1 --> C
//一、选择题
//1、有如下代码，则 * (p[0] + 1) 所代表的数组元素是（ ）
//int a[3][2] = { 1, 2, 3, 4, 5, 6 }, *p[3];
//p[0] = a[1];
//A: a[0][1]  B : a[1][0]  C : a[1][1]  D : a[1][2]




//x 2 --> ABD  void* 相当于一个垃圾桶哦
//2、关于指针下列说法正确的是【多选】（ ）
//A : 任何指针都可以转化为void * B : void* 可以转化为任何指针
//C : 指针的大小为8个字节 D : 指针虽然高效、灵活但可能不安全




//x 3 --> D 没有取地址
//3、以下 scanf 函数调用选项中， 错误的是（ ）
//struct T
//{
//	char name[20];
//	int age;
//	int sex;
//} a[5], * pa = a;
//A: scanf("%s", a[0].name); B: scanf("%d", &pa[0].age);
//C: scanf("%d", &(pa->age)); D: scanf("%d", pa->age);




//x 4 --> A
// 依题目已知情况，当n<=12时结果是正确的，说明是随着参数的变大计算过程中哪里出了问题，故而要在prod *= i;处设断
//点，查看原因。错误原因是数据过大时整型溢出
//4、如下函数 fun 计算 prod = 1 * 2 * 3 * … * n ，并返回计算结果值。但当 n > 12 时，返回值不正确。要找出该程序的错
//误，正确的调试方法是（ ）
//int fun(int n)
//{
//	int prod = 1, i = 0;
//	for (i = 1; i <= n; i++)
//	{
//		prod *= i;
//	}
//	return prod;
//}
//A: 监视变量prod的值，在prod *= i; 行处设置断点，然后单步运行，直到发现错误原因
//B : 监视变量prod的值，在return prod; 行处设置断点，程序中断后，即可发现错误原因
//C : 在prod = 1; 处设置断点，然后在函数调用堆栈中即可发现错误原因
//D : 监视变量i的值，在for(i = 1; i <= n; i++)行处设置断点，然后单步运行，直到发现错误原因




//x 5 --> D
//5、下列给定程序中，函数 fun 的功能是：把形参a所指数组中的奇数按原顺序依次存放到 a[0]、a[1]、a[2]… 中，把
//偶数从数组中删除，奇数个数通过函数值返回。 例如，若a所指数组中的数据最初排列为： 
// 9, 1, 4, 2, 3, 6, 5, 8, 7 ，删除偶数后，a所指数组中的数据为： 
// 9, 1, 3, 5, 7 ，返回值为5。请在程序的下画线处填入正确的内容并将下画线删除，使
//程序得出正确的结果（ ）
//int fun(int a[], int n)
//{
//	int i, j;
//	j = 0;
//	for (i = 0; i < n; i++)
//		if (a[i] % 2 == ____1_____)
//		{
//			a[j] = a[i];
//			___j++______;
//		}
//	return _____j____;
//}
//A: 0 j++ j B : 1 j++ j + 1 C : 0 j++ j + 1 D : 1 j++ j



//二、编程题
//KS33 寻找奇数 
//现在有一个长度为 n 的正整数序列，其中只有一种数值出现了奇数次，其他数值均出现偶数次，请你找出那个出现奇数次的数值。
//数据范围：1≤n≤2×106 1≤n≤2×106
//输入描述：
//第一行：一个整数n，表示序列的长度。第二行：n个正整数ai，两个数中间以空格隔开。
//输出描述：
//一个数，即在序列中唯一出现奇数次的数值。
//输入：
//5
//2 1 2 3 1
//输出：3
//https://www.nowcoder.com/practice/849b9e545f4742398d278f5dc4e003d2?tpId=182&&tqId=34478&rp=1&ru=/ta/exam-all&qru=/ta/exam-all/question-ranking
//错误的 因为输入的数据可能是 比2*10^6还要大的数
// int main() 
// {
//     int n = 0; int arr[2000001]={0};int find[2000001]={0};
//     scanf("%d",&n);
//     int i = 0;
//     for(i=0; i<n; i++)
//     {
//         scanf("%d ", &arr[i]);
//         find[arr[i]] += 1;
//     }
//     for(i=0; i<n; i++)
//     {
//         if(find[i]==0)
//             continue;
//         if(find[i]%2==1)
//         {
//             break;
//         }
//     }
//     printf("%d\n", arr[i]);
//     return 0;
// }


//*************************************************//
//采用异或的方式 因为两个相同的数字异或=0(比特位相同) 如果是偶数位的话岂不是
//都是0了，只有奇数位留下了一个数 0与任何数异或都是数本身
// ^能交换顺序哦  2^3^4^5^4^5^3 -> 2^(3^3)^(4^4)^(5^5) -> 2^0 = 2
// 异或 专业找单身
//*************************************************//
//int main()
//{
//    int n = 0;
//    while (~scanf("%d", &n))
//    {
//        int num = 0; int tmp = 0;
//        int i = 0;
//        for (i = 0; i < n; i++)
//        {
//            scanf("%d ", &tmp);
//            num ^= tmp;
//        }
//        printf("%d\n", num);
//    }
//    return 0;
//}





//b2
//NC107 寻找峰值
//给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。
//1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
//2.假设 nums[-1] = nums[n] = −∞−∞
//3.对于所有有效的 i 都有 nums[i] != nums[i + 1]
//4.你可以使用O(logN)的时间复杂度实现此问题吗？
//数据范围：
//1≤nums.length≤2×105 1≤nums.length≤2×105
//−231 <= nums[i] <= 231−1−231 <= nums[i] <= 231−1
//如输入[2, 4, 1, 2, 7, 8, 4]时，会形成两个山峰，一个是索引为1，峰值为4的山峰，另一个是索引为5，峰值为8的山峰，如下图所示：
//输入：[2, 4, 1, 2, 7, 8, 4]
//返回值：1
//说明：4和8都是峰值元素，返回4的索引1或者8的索引5都可以
//https://www.nowcoder.com/practice/fcf87540c4f347bcb4cf720b5b350c76?tpId=188&&tqId=38666&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking
/*
* @param nums int整型一维数组
* @param numsLen int nums数组长度
* @return int整型
*/
//用二分法更高效凹  其实就是找到 左边递增右边递减 这样一个数位置
int findPeakElement(int* nums, int numsLen)
{
    //判断边缘的峰值
    if (nums[0] > nums[1])
        return 0;
    if (nums[numsLen - 1] > nums[numsLen - 2])
        return numsLen - 1;

    int left = 0; int right = numsLen - 1;
    while (left < right)
    {
        int mid = (left + right) / 2;
        if (nums[mid] < nums[mid + 1]) //说明从左网友是递增的
        {
            left = mid + 1;
        }
        else
        {
            right = mid;
        }
    }
    return left;
}
